
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {
    private TreeNode prev = null; // 上一个访问过的节点，用于构建双向链表的链接

    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }

        // 将当前子树转换为排序的双向链表
        convertTreeToLinkedList(pRootOfTree);

        // 找到双向链表的头节点并返回
        TreeNode head = pRootOfTree;
        while (head.left != null) {
            head = head.left;
        }

        return head;
    }

    // 中序遍历二叉搜索树，将其转换为排序的双向链表
    private void convertTreeToLinkedList(TreeNode root) {
        if (root == null) {
            return;
        }

        // 处理左子树
        convertTreeToLinkedList(root.left);

        // 连接当前节点与前一个节点（后继节点的左指针指向前一个节点）
        root.left = prev;
        if (prev != null) {
            prev.right = root;
        }
        prev = root;

        // 处理右子树
        convertTreeToLinkedList(root.right);
    }
}